Матч 305, Мультичтение (MultiRead)

Дивизион 2, Уровень 1

В компьютерных системах несколько процессов могут одновременно читать данные, но только один процесс может выполнять операцию записи в течение одного такта времени. Строка trace содержит историю работы системы и состоит из символов ‘R’ (чтение) и ‘W’ (запись). Вычислить минимальное время, за которое могут быть произведены все операции procs процессами.

Класс: MultiRead

Метод: int minCycles(string trace, int procs)

Ограничения: trace содержит от 1 до 50 символов ‘R’ и ‘W’, 1 £ procs £ 10.

Вход. Строка trace и число procs.

Выход. Количество тактов времени, за которое может быть выполнена последовательность операций чтения/записи, заданная строкой trace, procs процессами.

Пример входа

trace	procs
“RWWRRR”	3
“RWWRRRR”	3
“RRRRRRRRRR”	4

Пример выхода

4

5

3

РЕШЕНИЕ

обработка строк

Просматриваем строку trace. При встрече операции записи увеличиваем искомое число тактов времени res на 1. Длину каждой группы из операций чтения заносим в переменную с. с операций чтения можно выполнить procs процессами за временных тактов. Заметим, что

= (c + procs – 1) / procs,

где деление является целочисленным. Добавим это число к переменной res.

ПРОГРАММА

#include <cstdio>

#include <string>

using namespace std;

class MultiRead

{

public:

int minCycles(string trace, int procs)

{

int res, i, c;

for(res = i = 0; i < trace.size(); i++)

if (trace[i] == 'W') res++; else

{

c = 0; while((trace[i] == 'R') && (i < trace.size())) {c++; i++;} i--;

res += (c + procs - 1) / procs;

}

return res;

}

};